Search for: All records

Polyploidy and subsequent post-polyploid diploidization (PPD) are key drivers of plant genome evolution, yet their contributions to evolutionary success remain debated. Here, we analyze the Malvaceae family as an exemplary system for elucidating the evolutionary role of polyploidy and PPD in angiosperms, leveraging 11 high-quality chromosome-scale genomes from all nine subfamilies, including newly sequenced, near telomere-to-telomere assemblies from four of these subfamilies. Our findings reveal a complex reticulate paleoallopolyploidy history early in the diversification of the Malvadendrina clade, characterized by multiple rounds of species radiation punctuated by ancient allotetraploidization (Mal-β) and allodecaploidization (Mal-α) events around the Cretaceous–Paleogene (K–Pg) boundary. We further reconstruct the evolutionary dynamics of PPD and find a strong correlation between dysploidy rate and taxonomic richness of the paleopolyploid subfamilies (R^2 ≥ 0.90, P < 1e-4), supporting the “polyploidy for survival and PPD for success” hypothesis. Overall, our study provides a comprehensive reconstruction of the evolutionary history of the Malvaceae and underscores the crucial role of polyploidy–dysploidy waves in shaping plant biodiversity. 

Polynomial partitioning techniques have recently led to improved geometric data structures for a variety of fundamental problems related to semialgebraic range searching and intersection searching in 3D and higher dimensions (e.g., see [Agarwal, Aronov, Ezra, and Zahl, SoCG 2019; Ezra and Sharir, SoCG 2021; Agarwal, Aronov, Ezra, Katz, and Sharir, SoCG 2022]). They have also led to improved algorithms for offline versions of semialgebraic range searching in 2D, via lens-cutting [Sharir and Zahl (2017)]. In this paper, we show that these techniques can yield new data structures for a number of other 2D problems even for online queries: 1) Semialgebraic range stabbing. We present a data structure for n semialgebraic ranges in 2D of constant description complexity with O(n^{3/2+ε}) preprocessing time and space, so that we can count the number of ranges containing a query point in O(n^{1/4+ε}) time, for an arbitrarily small constant ε > 0. (The query time bound is likely close to tight for this space bound.) 2) Ray shooting amid algebraic arcs. We present a data structure for n algebraic arcs in 2D of constant description complexity with O(n^{3/2+ε}) preprocessing time and space, so that we can find the first arc hit by a query (straight-line) ray in O(n^{1/4+ε}) time. (The query bound is again likely close to tight for this space bound, and they improve a result by Ezra and Sharir with near n^{3/2} space and near √n query time.) 3) Intersection counting amid algebraic arcs. We present a data structure for n algebraic arcs in 2D of constant description complexity with O(n^{3/2+ε}) preprocessing time and space, so that we can count the number of intersection points with a query algebraic arc of constant description complexity in O(n^{1/2+ε}) time. In particular, this implies an O(n^{3/2+ε})-time algorithm for counting intersections between two sets of n algebraic arcs in 2D. (This generalizes a classical O(n^{3/2+ε})-time algorithm for circular arcs by Agarwal and Sharir from SoCG 1991.) 

In the Directed Steiner Tree (DST) problem the input is a directed edge-weighted graph G = (V,E), a root vertex r and a set S ⊆ V of k terminals. The goal is to find a min-cost subgraph that connects r to each of the terminals. DST admits an O(log² k/log log k)-approximation in quasi-polynomial time [Grandoni et al., 2022; Rohan Ghuge and Viswanath Nagarajan, 2022], and an O(k^{ε})-approximation for any fixed ε > 0 in polynomial-time [Alexander Zelikovsky, 1997; Moses Charikar et al., 1999]. Resolving the existence of a polynomial-time poly-logarithmic approximation is a major open problem in approximation algorithms. In a recent work, Friggstad and Mousavi [Zachary Friggstad and Ramin Mousavi, 2023] obtained a simple and elegant polynomial-time O(log k)-approximation for DST in planar digraphs via Thorup’s shortest path separator theorem [Thorup, 2004]. We build on their work and obtain several new results on DST and related problems. - We develop a tree embedding technique for rooted problems in planar digraphs via an interpretation of the recursion in [Zachary Friggstad and Ramin Mousavi, 2023]. Using this we obtain polynomial-time poly-logarithmic approximations for Group Steiner Tree [Naveen Garg et al., 2000], Covering Steiner Tree [Goran Konjevod et al., 2002] and the Polymatroid Steiner Tree [Gruia Călinescu and Alexander Zelikovsky, 2005] problems in planar digraphs. All these problems are hard to approximate to within a factor of Ω(log² n/log log n) even in trees [Eran Halperin and Robert Krauthgamer, 2003; Grandoni et al., 2022]. - We prove that the natural cut-based LP relaxation for DST has an integrality gap of O(log² k) in planar digraphs. This is in contrast to general graphs where the integrality gap of this LP is known to be Ω(√k) [Leonid Zosin and Samir Khuller, 2002] and Ω(n^{δ}) for some fixed δ > 0 [Shi Li and Bundit Laekhanukit, 2022]. - We combine the preceding results with density based arguments to obtain poly-logarithmic approximations for the multi-rooted versions of the problems in planar digraphs. For DST our result improves the O(R + log k) approximation of [Zachary Friggstad and Ramin Mousavi, 2023] when R = ω(log² k). 

Carbon nanotube (CNT)/epoxy nanocomposites have a great potential of possessing many advanced properties. However, the homogenization of CNT dispersion is still a great challenge in the research field of nanocomposites. This study applied a novel dispersion agent, carboxymethyl cellulose (CMC), to functionalize CNTs and improve CNT dispersion in epoxy. The effectiveness of the CMC functionalization was compared with mechanical mixing and a commonly used surfactant, sodium dodecylbenzene sulfonate (NaDDBS), regarding dispersion, mechanical and corrosion properties of CNT/epoxy nanocomposites with three different CNT concentrations (0.1%, 0.3% and 0.5%). The experimental results of Raman spectroscopy, particle size analysis and transmission electron microscopy showed that CMC functionalized CNTs reduced CNT cluster sizes more efficiently than NaDDBS functionalized and mechanically mixed CNTs, indicating a better CNT dispersion. The peak particle size of CMC functionalized CNTs reduced as much as 54% (0.1% CNT concentration) and 16% (0.3% CNT concentration), compared to mechanical mixed and NaDDBS functionalized CNTs. Because of the better dispersion, it was found by compressive tests that CNT/epoxy nanocomposites with CMC functionalization resulted in 189% and 66% higher compressive strength, 224% and 50% higher modulus of elasticity than those with mechanical mixing and NaDDBS functionalization respectively (0.1% CNT cencentration). In addition, electrochemical corrosion tests also showed that CNT/epoxy nanocomposites with CMC functionalization achieved lowest corrosion rate (0.214 mpy), the highest corrosion resistance (201.031 Ω·cm2), and the lowest porosity density (0.011%). 

Abstract Rapid progress in machine learning offers new opportunities for the automated analysis of multidimensional NMR spectra ranging from protein NMR to metabolomics applications. Most recently, it has been demonstrated how deep neural networks (DNN) designed for spectral peak picking are capable of deconvoluting highly crowded NMR spectra rivaling the facilities of human experts. Superior DNN-based peak picking is one of a series of critical steps during NMR spectral processing, analysis, and interpretation where machine learning is expected to have a major impact. In this perspective, we lay out some of the unique strengths as well as challenges of machine learning approaches in this new era of automated NMR spectral analysis. Such a discussion seems timely and should help define common goals for the NMR community, the sharing of software tools, standardization of protocols, and calibrate expectations. It will also help prepare for an NMR future where machine learning and artificial intelligence tools will be common place.